home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / AVL_Tree.h < prev    next >
C/C++ Source or Header  |  1992-05-15  |  5KB  |  135 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/28/89 -- Initial design and implementation
  13. // Updated: MBN 08/20/89 -- Updated template usage to reflect new syntax
  14. // Updated: MBN 09/19/89 -- Added conditional exception handling
  15. // Updated: DKM 11/05/89 -- Replaced re-balance after exceeding goal height
  16. //                          with true AVL rotation alorythm.
  17. // Updated: LGO 12/04/89 -- operator<< not inline
  18. // Updated: LGO 12/04/89 -- balance not inline
  19. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  20. // Updated: VDN 02/21/92 -- New lite version
  21. //
  22. // The AVL_Tree<Type> class implements height-balanced, dynamic,  binary trees.
  23. // The  AVL_Tree<Type> class is  publicly derived   from  the Binary_Tree<Type>
  24. // class and  both  are parameterized  over some type   Type. An AVL  tree is a
  25. // compromise  between the  expense  of a  fully balanced binary  tree and  the
  26. // desire for efficient search times for both average and worst case scenarios.
  27. // As a result, an AVL tree  maintains a  binary tree that  is height-balanced,
  28. // insuring that the minimum and maximum depth  of any path  through the binary
  29. // tree is within some specified range.
  30. //
  31. // The  AVL_Tree<Type>  class has  no private  data slots   and only two public
  32. // constructors.  The first constructor  takes an optional argument that allows
  33. // the user  to  specify  the height-balance limit  (the   default is  two).  A
  34. // height-balance  value   of  zero indicates    that  the  tree should  remain
  35. // completely balanced.   The second  constructor  takes a reference to another
  36. // AVL_Tree<Type> and duplicates its size and values.
  37. //
  38. // The  AVL_Tree<Type>  class   inherits  all its   methods  publicly from  the
  39. // Binary_Tree<Type> class. The only methods that are overloaded are those that
  40. // affect  the structure of  the tree, thus  potentially requiring  one or more
  41. // subtrees to be shaken and restructured.
  42. //
  43.  
  44. #ifndef AVL_TREEH                // If no definition for class
  45. #define AVL_TREEH
  46.  
  47. #ifndef BINARY_TREEH                // If no definition for class
  48. #include <cool/Binary_Tree.h>            // include definition file
  49. #endif
  50.  
  51. // DECLARE CoolBinary_Tree<Type>, but ensure it's only done once.
  52. template <class Type> CoolAVL_Tree {
  53. #ifndef DECLARE_CoolBinary_Tree_##Type
  54. #define DECLARE_CoolBinary_Tree_##Type
  55.   DECLARE CoolBinary_Tree<Type>;
  56. #endif
  57. }
  58.  
  59. #define CoolAVL_Tree_state CoolBT_State
  60.  
  61. template <class Type>
  62. class CoolAVL_Tree<Type> : public CoolBinary_Tree<Type> {
  63.   
  64. public:
  65.   inline CoolAVL_Tree<Type> () {};            // Simple constructor
  66.   CoolAVL_Tree<Type> (const CoolAVL_Tree<Type>&);    // Copy constructor
  67.   CoolAVL_Tree<Type> (const CoolBinary_Tree<Type>&);    // Convert BT into AVL
  68.   ~CoolAVL_Tree<Type> ();                // Destructor
  69.  
  70.   inline Boolean put (const Type&);        // Add an item to tree
  71.   inline Boolean remove (const Type&);        // Remove item from tree
  72.   inline Boolean remove ();            // Remove item current position
  73.   void balance ();                // Special balance for AVL
  74.   inline CoolAVL_Tree<Type>& operator= (CoolAVL_Tree<Type>&);  // Assignment overloaded
  75.   inline CoolAVL_Tree<Type>& operator= (CoolBinary_Tree<Type>&);//Assignment overloaded
  76.   friend ostream& operator<< (ostream&, const CoolAVL_Tree<Type>&);
  77.   inline friend ostream& operator<< (ostream&, const CoolAVL_Tree<Type>*);
  78. };
  79.  
  80.  
  81. // put -- Add a value to the AVL tree if it is not already there and balance
  82. //        tree if necessary
  83. // Input: Reference to value to add to tree
  84. // Output: TRUE if item added, FALSE otherwise
  85.  
  86. template <class Type> 
  87. inline Boolean CoolAVL_Tree<Type>::put (const Type& value) {
  88.   return (CoolBinary_Tree<Type>::put_internal (value, TRUE)); 
  89. }
  90.  
  91.  
  92. // remove -- Remove a value from the AVL tree. Deletion of a node and balance
  93. //           tree if necessary
  94. // Input:    Reference to value to remove
  95. // Output:   TRUE if item removed, FALSE otherwise
  96.  
  97. template <class Type> 
  98. inline Boolean CoolAVL_Tree<Type>::remove (const Type& value) {
  99.   return (CoolBinary_Tree<Type>::remove_internal (value, TRUE)) ;
  100. }
  101.  
  102.  
  103. // remove -- Remove node at current position in the tree and balance tree
  104. // Input:    None
  105. // Output:   Value of node removed from tree
  106.  
  107. template <class Type> 
  108. inline Boolean CoolAVL_Tree<Type>::remove () {
  109.   return (CoolBinary_Tree<Type>::remove_internal(this->value(),TRUE));
  110. }
  111.  
  112.  
  113. template <class Type> 
  114. inline CoolAVL_Tree<Type>& CoolAVL_Tree<Type>::operator= (CoolAVL_Tree<Type>& av) {
  115.   CoolBinary_Tree<Type>::operator= (av);    // Create the new Tree
  116.   return *this;                    // Return tree reference
  117. }
  118.  
  119. template <class Type>
  120. inline CoolAVL_Tree<Type>& CoolAVL_Tree<Type>::operator= (CoolBinary_Tree<Type>& bt) {
  121.   CoolBinary_Tree<Type>::operator= (bt);    // Create the new Tree
  122.   this->balance();                // Do an AVL balance
  123.   return *this;                    // Return tree reference
  124. }
  125.  
  126.  
  127.  
  128. template<class Type> CoolAVL_Tree {
  129. inline ostream& operator<< (ostream& os, const CoolAVL_Tree<Type>* av) {
  130.   return operator<< (os, *av);
  131. }
  132. }
  133.  
  134. #endif                        // End AVL_TREEH #if
  135.